package com.yileiqian.util;

public class BinaryTree {
	public static BinaryTree getTree(int[] array) {
		if (array.length == 0) {
			return null;
		}

		BinaryTree tree = new BinaryTree(array[0]);

		insert(array, 1, tree.getRoot());

		return tree;
	}

	private static void insert(int[] array, int parent, BTNode node) {
		int left = 2 * parent;
		int right = 2 * parent + 1;

		if (left - 1 < array.length) {
			BTNode child = new BTNode(array[left - 1]);
			node.left = child;
			insert(array, left, child);
		}
		if (right - 1 < array.length) {
			BTNode child = new BTNode(array[right - 1]);
			node.right = child;
			insert(array, right, child);
		}

	}

	private BinaryTree(int value) {
		root = new BTNode(value);
	}

	private BTNode root;

	public BTNode getRoot() {
		return root;
	}

	public void printTree(BTNode node) {
		if (node == null) {
			return;
		}

		printTree(node.left);
		System.out.print(node.value + " ");
		printTree(node.right);

	}

	public String printTreePreOrder() {
		StringBuffer buffer = new StringBuffer("PreOrder: ");
		Stack<BTNode> stack = new Stack<BTNode>();

		stack.push(root);

		while (stack.hasNext()) {
			BTNode node = stack.pop();

			buffer.append(node.value);
			buffer.append(' ');

			if (node.right != null) {
				stack.push(node.right);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
		}

		buffer.append('\n');
		return buffer.toString();
	}

	public String printTreeInOrder() {
		StringBuffer buffer = new StringBuffer("InOrder: ");
		Stack<BTNode> stack = new Stack<BTNode>();

		if (root == null) {
			return buffer.toString();
		}

		stack.push(root);


		return buffer.toString();
	}

	public String printTreeProOrder() {
		StringBuffer buffer = new StringBuffer("ProOrder: ");
		Stack<BTNode> stack = new Stack<BTNode>();

		stack.push(root);

		BTNode p = root, q = root;

		while (p != null) {
			while (p.left != null) {
				stack.push(p);
				p = p.left;
			}

			while (p.right == null || p.right == q) {

				buffer.append(p.value);
				buffer.append(' ');

				q = p;
				if (!stack.hasNext()) {
					break;
				}
				p = stack.pop();
			}

			stack.push(p);
			p = p.right;
		}

		return buffer.toString();
	}

	public String printTreeByLine() {
		StringBuffer buffer = new StringBuffer();

		Queue<BTNode> q1 = new Queue<BTNode>();
		Queue<BTNode> q2 = new Queue<BTNode>();

		q1.enqueue(root);

		while (q1.hasNext() || q2.hasNext()) {
			if (q1.hasNext()) {
				BTNode node = q1.dequeue();

				buffer.append(node.value);
				buffer.append(' ');

				if (node.left != null) {
					q2.enqueue(node.left);
				}
				if (node.right != null) {
					q2.enqueue(node.right);
				}
			} else {
				buffer.append('\n');
				Queue<BTNode> tq = q1;
				q1 = q2;
				q2 = tq;
			}
		}

		buffer.append('\n');

		return buffer.toString();
	}
	
	
	
	public static void main(String args[]) {

		int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
		BinaryTree tree = BinaryTree.getTree(array);
		System.out.println(tree.printTreeByLine());
		
		System.out.println();
		System.out.println(tree.printTreePreOrder());

		System.out.println(tree.printTreeProOrder());

		// tree.printTree(tree.root);
		System.out.println();
		System.out.println(tree.printTreeInOrder());
	}

}

class BTNode {
	public BTNode left;
	public BTNode right;
	public int value;

	public BTNode(int value) {
		this.value = value;
	}
}
